package model;

import java.util.ArrayList;
import java.util.List;

/**
 * class that generates a list of strings that represent expressions which evaluate to the goal
 * 
 * @author Karen Berntsen (s0815799)
 * @author Erik Stens (s0615374)
 */
public class ExpressionGenerator {
	private int	numbers[];
	
	/**
	 * Constructor defines row of numbers
	 * 
	 * @param row
	 */
	public ExpressionGenerator(int[] row) {
		numbers = row;
	}
	
	/**
	 * generates a list of strings that represent expressions which evaluate to the goal
	 * 
	 * @param goal
	 * @return the list of solutions as strings
	 */
	public List<String> search(int goal) {
		ArrayList<String> trace = new ArrayList<String>();
		ArrayList<String> solutions = new ArrayList<String>();
		search(0, 0, goal, trace, solutions);
		return solutions;
	}
	
	/**
	 * The actual backtracking algorithm
	 * 
	 * @param current
	 *            the result of the expression up till now
	 * @param index
	 *            of the next candidate number in the row of numbers
	 * @param goals
	 *            the number that the expression evaluates to
	 * @param trace
	 *            the list of strings that represents the expression so far
	 * @return the list of strings that contains all solutions)
	 */
	private List<String> search(int current, int index, int goals, List<String> trace, List<String> solutions) {
		if (current == goals && index == numbers.length) {
			solutions.add(solutionToString(trace));
		}
		
		if (index > numbers.length - 1) {
			return trace;
		}
		
		if (trace.isEmpty()) {
			current = numbers[index];
			trace.add(Integer.toString(numbers[index]));
			trace = search(current, index + 1, goals, trace, solutions);
			trace.clear();
			
			trace = search(current, index + 1, goals, trace, solutions);
		} else {
			trace.add(" * " + numbers[index]);
			trace = search(current * numbers[index], index + 1, goals, trace, solutions);
			trace.remove(trace.size() - 1);
			
			if (current % numbers[index] == 0) {
				trace.add(" / " + numbers[index]);
				trace = search(current / numbers[index], index + 1, goals, trace, solutions);
				trace.remove(trace.size() - 1);
			}
			
			trace.add(" + " + numbers[index]);
			trace = search(current + numbers[index], index + 1, goals, trace, solutions);
			trace.remove(trace.size() - 1);
			
			trace.add(" - " + numbers[index]);
			trace = search(current - numbers[index], index + 1, goals, trace, solutions);
			trace.remove(trace.size() - 1);
			
			trace = search(current, index + 1, goals, trace, solutions);
		}
		
		return trace;
	}
	
	/**
	 * @param stringList
	 * @return string of the concatenation of all elements of stringList
	 */
	private String solutionToString(List<String> stringList) {
		StringBuilder sb = new StringBuilder();
		for (String string : stringList) {
			sb.append(string);
		}
		return sb.toString();
	}
}
